//https://leetcode.cn/problems/minimum-cost-tree-from-leaf-values/submissions/589197939/
class Solution {
public:
    int mctFromLeafValues(vector<int>& arr) {
        int ans = 0;
        while (arr.size() > 1) {
            int idx = 0, adj = INT_MAX;
            for (int i = 0; i < arr.size() - 1; ++i) {
                int tmp = arr[i] * arr[i + 1];
                if (tmp < adj) {
                    adj = tmp;
                    idx = i;
                }
            }
            ans += adj;
            if (arr[idx] < arr[idx + 1]) arr.erase(arr.begin() + idx);
            else arr.erase(arr.begin() + idx + 1);
        }
        return ans;
    }
};